package _447

import "fmt"

//给你一个整数 n ，请你返回所有 0 到 1 之间（不包括 0 和 1）满足分母小于等于 n 的 最简 分数 。分数可以以 任意 顺序返回。
//
//
//
// 示例 1：
//
// 输入：n = 2
//输出：["1/2"]
//解释："1/2" 是唯一一个分母小于等于 2 的最简分数。
//
// 示例 2：
//
// 输入：n = 3
//输出：["1/2","1/3","2/3"]
//
//
// 示例 3：
//
// 输入：n = 4
//输出：["1/2","1/3","1/4","2/3","3/4"]
//解释："2/4" 不是最简分数，因为它可以化简为 "1/2" 。
//
// 示例 4：
//
// 输入：n = 1
//输出：[]
//
//
//
//
// 提示：
//
//
// 1 <= n <= 100
//
// Related Topics 数学 字符串 数论 👍 61 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
func simplifiedFractions(n int) []string {
	var result []string
	for i := 2; i <= n; i++ {
		for j := 1; j < i; j++ {
			if gcd(i, j) == 1 {
				result = append(result, fmt.Sprintf("%d/%d", j, i))
			}
		}
	}
	return result
}

func gcd(a, b int) int {
	for a != 0 {
		a, b = b % a, a
	}
	return b
}
//leetcode submit region end(Prohibit modification and deletion)
type ListNode struct {
    Val int
    Next *ListNode
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
	// 将最终结果存到l1中
	result := l1
	for {
		if l1 == nil && l2 == nil {
			break
		}
		add := 0
		if l1 != nil {
			add += l1.Val
		}
		if l2 != nil {
			add += l2.Val
			l2 = l2.Next
		}
		if l1.Next != nil {
			l1.Next.Val += add / 10
		} else {
			l1.Next = &ListNode{
				Val: add / 10,
			}
		}
		add = add % 10
		l1.Val = add
		l1 = l1.Next
	}
	return result
}